package com.chj.gaoji.class15;

public class Code05_StrangePrinter {
	public static int strangePrinter(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		char[] str = s.toCharArray();
		int N = str.length;
		int[][] dp = new int[N][N];
		dp[N - 1][N - 1] = 1;
		for (int i = 0; i < N - 1; i++) {
			dp[i][i] = 1;
			dp[i][i + 1] = str[i] == str[i + 1] ? 1 : 2;
		}
		for (int i = N - 2; i >= 0; i--) {
			for (int j = i + 2; j < N; j++) {
				dp[i][j] = j - i + 1;
				for (int k = i + 1; k <= j; k++) {
					dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + dp[k][j] - (str[i] == str[k] ? 1 : 0));
				}
			}
		}
		return dp[0][N - 1];
	}

	public static int strangePrinter02(String s) {

		int n = s.length();
		if (n == 0)
			return 0;
		int[][] dp = new int[n + 1][n + 1];

		for (int i = 0; i < n; i++) {
			dp[i][i] = 1;
		}
		for (int len = 2; len <= n; len++) {
			for (int i = 0; i + len - 1 < n; i++) {
				int j = i + len - 1;
				dp[i][j] = dp[i + 1][j] + 1;
				for (int k = i + 1; k <= j; k++) {
					if (s.charAt(i) == s.charAt(k))
						dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + dp[k + 1][j]);
				}
			}
		}
		return dp[0][n - 1];
	}

//	作者：GitKid
//	链接：https://leetcode-cn.com/problems/strange-printer/solution/java-yan-shi-dpfen-xi-fa-qu-jian-dp-qing-xi-yi-don/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	public static void main(String[] arg) {
		System.out.println(strangePrinter("aba"));
		System.out.println(strangePrinter("aaabbb"));

		System.out.println(strangePrinter02("aba"));
		System.out.println(strangePrinter02("aaabbb"));
	}
}
